package ali;

import java.util.*;

/**
 * @author xizizzz
 * @description: TODO
 * @date 2021-9-8上午 09:02
 */
public class Test1 {
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            final String binary = binary(n, k);
            final String s = new StringBuilder(binary).reverse().toString();
            final Long num = Long.valueOf(s, k);
            System.out.println(num);
        }
    }

    public static String binary(int n, int b) {
        if (n < b) {
            if (n < 10)
                return String.valueOf(n);
            else if (10 == n)
                return "A";
            else if (11 == n)
                return "B";
            else if (12 == n)
                return "C";
            else if (13 == n)
                return "D";
            else if (14 == n)
                return "E";
            else
                return "F";
        } else {
            if ((n % b) < 10)
                return binary(n / b, b).concat(String.valueOf(n % b));
            if ((n % b) == 10)
                return binary(n / b, b).concat("A");
            else if ((n % b) == 11)
                return binary(n / b, b).concat("B");
            else if ((n % b) == 12)
                return binary(n / b, b).concat("C");
            else if ((n % b) == 13)
                return binary(n / b, b).concat("D");
            else if ((n % b) == 14)
                return binary(n / b, b).concat("E");
            else
                return binary(n / b, b).concat("F");
        }
    }
}
